import java.util.*;

class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
     TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }

public class Test {
    // 题目1：左叶子节点
    int sum;
    public int sumOfLeftLeaves(TreeNode root) {
        dsf(root, false);
        return sum;
    }

    private void dsf(TreeNode root, boolean isLeft){
        if(root == null){
            return;
        }

        if(root.left == null && root.right == null && isLeft){
            sum += root.val;
        }

        dsf(root.left, true);
        dsf(root.right, false);
    }

    // 题目2：叶子相似的树
    public boolean leafSimilar(TreeNode root1, TreeNode root2) {
        List<Integer> list1 = new LinkedList<>();
        List<Integer> list2 = new LinkedList<>();

        dsf(list1, root1);
        dsf(list2, root2);

        return list1.equals(list2);
    }

    private void dsf(List<Integer> list, TreeNode root){
        if(root == null){
            return;
        }

        if(root.left == null && root.right == null){
            list.add(root.val);
        }

        dsf(list, root.left);
        dsf(list, root.right);
    }

    //题目3： 二叉树的前序遍历
    // morris
    public List<Integer> preorderTraversal1(TreeNode root) {
        TreeNode cur = root;
        TreeNode rightMost = null;
        List<Integer> list = new LinkedList<>();
        while(cur != null){
            rightMost = cur.left;
            if(rightMost != null){
                while(rightMost.right != null && rightMost.right != cur){
                    rightMost = rightMost.right;
                }
                if(rightMost.right == null){
                    rightMost.right = cur;
                    list.add(cur.val);
                    cur = cur.left;
                }else{
                    rightMost.right = null;
                    cur = cur.right;
                }
            }else{
                list.add(cur.val);
                cur = cur.right;
            }
        }
        return list;
    }

    //题目4：  二叉搜索树的最小绝对差
    int pre = -1;
    int min = Integer.MAX_VALUE;
    public int getMinimumDifference(TreeNode root) {
        dsf(root);
        return min;
    }
    private void dsf(TreeNode root){
        if(root == null){
            return ;
        }

        dsf(root.left);
        if(pre != -1){
            min = Math.min(min, root.val - pre);
        }
        pre = root.val;
        dsf(root.right);
    }

    // 题目5：数组中的 k-diff 数对
    // 给你一个整数数组 nums 和一个整数 k，请你在数组中找出 不同的 k-diff 数对，并返回不同的 k-diff 数对 的数目。
    //
    //k-diff 数对定义为一个整数对 (nums[i], nums[j]) ，并满足下述全部条件：
    //
    //0 <= i, j < nums.length
    //i != j
    //|nums[i] - nums[j]| == k
    //注意，|val| 表示 val 的绝对值。
    public int findPairs(int[] nums, int k) {
        Set<Integer> visited = new HashSet<>();
        Set<Integer> res = new HashSet<>();

        for(int num : nums){
            if(visited.contains(num + k)){
                res.add(num + k);
            }
            if(visited.contains(num - k)){
                res.add(num);
            }
            visited.add(num);
        }
        return res.size();
    }

    // 题目6 ：二叉树的坡度
    int sum1 = 0;
    public int findTilt(TreeNode root) {
        dsf1(root);
        return sum1;
    }

    private int dsf1(TreeNode root){
        if(root == null){
            return 0;
        }
        int left = dsf1(root.left);
        int right = dsf1(root.right);

        sum1 += Math.abs(left - right);

        return left + right + root.val;
    }

    // 题目7：二叉树中第二小的节点
    int rootVal;
    int ans;
    public int findSecondMinimumValue(TreeNode root) {
        rootVal = root.val;
        ans = -1;
        dsf2(root);
        return ans;
    }

    private void dsf2(TreeNode root){
        if(root == null){
            return;
        }

        if(ans != -1 && root.val >= ans){
            return;
        }

        if(root.val > rootVal){
            ans = root.val;
        }
        dsf2(root.left);
        dsf2(root.right);
    }

    // 题目8：二叉搜索树中第K小的元素
    public int kthSmallest1(TreeNode root, int k) {
        Deque<Integer> queue = new LinkedList<>();
        dsf(root, queue);
        while(k > 1){
            queue.poll();
            k--;
        }
        return queue.poll();
    }

    private void dsf(TreeNode root, Deque<Integer> queue){
        if(root == null){
            return;
        }

        dsf(root.left, queue);

        queue.offer(root.val);

        dsf(root.right,queue);

    }



    // 可以在中序遍历的的时候，就顺便找第k个最小的，可以使用非递归的中序遍历
    // 复习一下三种非递归的遍历吧
    // 题目9：非递归前序遍历
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new LinkedList<>();
        if(root == null){
            return res;
        }
        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode node = root;
        while(node != null || !stack.isEmpty()){
            while(node != null){
                res.add(node.val);
                stack.push(node);
                node = node.left;
            }
            node = stack.pop();
            node = node.right;
        }
        return res;
    }

    // 题目10 ：非递归中序遍历
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new LinkedList<>();
        if(root == null){
            return res;
        }
        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode node = root;
        while(!stack.isEmpty() || node != null){
            while(node != null){

                stack.push(node);
                node = node.left;
            }
            node = stack.pop();
            res.add(node.val);
            node = node.right;
        }
        return res;
    }

    // 题目11 ：非递归后序遍历
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new LinkedList<>();
        if(root == null){
            return res;
        }
        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode node = root;
        TreeNode prev = null;
        while(!stack.isEmpty() || node != null){
            while(node != null){
                stack.push(node);
                node = node.left;
            }
            node = stack.pop();

            if(node.right==null||prev==node.right){
                res.add(node.val);
                prev=node;
                node=null;
            }else{

                stack.push(node);
                node=node.right;
            }
        }
        return res;
    }

    public int kthSmallest(TreeNode root, int k) {
        List<Integer> res = new LinkedList<>();
        TreeNode node = root;
        Deque<TreeNode> stack = new LinkedList<>();
        while(node != null || !stack.isEmpty()){
            while(node != null){
                stack.push(node);
                node = node.left;
            }
            node = stack.pop();
            k--;
            if(k < 1){
                break;
            }
            node = node.right;
        }
        return node.val;
    }




}
